﻿//给定一个 n 个节点的邻接矩阵 m。 
//节点定义为城市，如果 a 城市与 b 城市相连， b 与 c 城市相连，尽管 a 与 c 并不直接相连，
//但可以认为 a 与 c 相连，定义 a, b, c 是一个城市群。
//矩阵 m[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，否则表示不相连。
//请你找出共有多少个城市群。
//
//数据范围：1≤n≤200  ， 矩阵中只包含0和1
//
//输入：[[1, 1, 0], [1, 1, 0], [0, 0, 1]]
//返回值：2
//说明：1 2 相连，3 独立，因此是 3 个城市群。
//
//输入：[[1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1]]
//返回值：2
//说明：1 ， 2相连 ；2 ，3相连，4独立，因此是 1, 2, 3 属于一个城市群，4属于一个城市群。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param m int整型vector<vector<>>
     * @return int整型
     */
    bool vis[210] = { 0 }; // ⽤来标记当前位置是否已经搜索过
    int citys(vector<vector<int> >& m) {
        int n = m.size();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ret++;
                dfs(m, i);
            }
        }
        return ret;
    }
    void dfs(vector<vector<int> >& m, int pos) {
        vis[pos] = true;
        for (int i = 0; i < m.size(); i++) {
            if (!vis[i] && m[pos][i]) {
                dfs(m, i);
            }
        }
    }
};










